Floppyshop 2/Floppyshop - 2.zip/Floppyshop - 2.iso/diskmags/5791-.end/dmg-6143/lza_rept/compres4.txt

Text File | 1996-06-15 | 12KB | 241 lines

               Experiments in Data Compression IV
                    (or "The Need for Speed")
                         by John Kormylo
                         E.L.F. Software


Binary Search Tree

     The  LZA  algorithm  uses a binary  search  tree  to  locate
strings.   Specifically it consists of an array of structures  of
the form

typedef struct tree {
  struct tree *parent;  /* binary tree pointers, or NULL */
  struct tree *child1;  /* less than */
  struct tree *child2;  /* greater than */
  unsigned char *text;  /* string pointer */
  unsigned int count;   /* number of children + 1 */
  int first;            /* number of bytes common with parent */
 } TREE;

with  one structure for every string in the  dictionary.   (Note,
these  are not NULL terminated strings,  but it is easier to  say
"string"  than "block of 65 consecutive bytes.")  One would do  a
string  compare  to 'text' and move to 'child1' or  'child2'  and
repeat.   The  'parent' entry was used for  tree  balancing,  but
turns out not to be necessary.   The 'count' entry was used  both
for tree balancing and for coding,  and the 'first' entry was  an
attempt  to  reduce  the number of byte  comparisons  during  the
string compares.  (However, nothing guarentees that child strings
will have ANY bytes in common.)
     To locate the longest match one must search until you hit  a
NULL  pointer.   Given  the first (in search order) match  for  a
given  length,  one must search all child strings to  locate  the
most  recent matching string (for the FIFO buffer) or search  for
the lowest and highest matching strings (for the dictionary).


FIFO Buffer - Hash Table

     Actually,  the method developed in the last report was  more
of  a  cross  between  a  hash  table  and  binary  search  tree.
Specifically, it consisted of 16 byte structures of the form:

typedef struct hash {
  struct hash *child1;    /* less than */
  struct hash *child2;    /* greater than */
  struct hash *next;      /* start of next tree */
  unsigned int sum;       /* sum of all matching strings */
  unsigned char index;    /* index of most recent match */
  unsigned char test;     /* character */
 } HASH;

Given a pointer to the start of the table,  one would search  for
the  first  byte in the string using a binary search  tree  using
'child1',  'child2',  and 'test'.   Once you have found the first
byte,  you can search for the second byte using the binary search
tree which starts at 'next'.  'Sum' is used by the tree balancing
algorithm,  and 'index' is the array index for the  corresponding
string in the FIFO buffer.
     The  number of structures used is variable,  with the  worst
case being 64 * 65 * sizeof(HASH) = 65K bytes, since there are 64
strings in the FIFO buffer, and each string has at most 65 bytes.
The  structures are initialized as a simple linked list  of  free
structures.   Also,  you will need an array of 64 string pointers
and weights.   (The hash table is used for coding only.)
     The  advantage  of this approach is that  we  have  replaced
string  compares  with byte compares.   Once the  first  byte  is
found, one need only search for the second bytes, etc.  Also, the
'index' value is automatically reset each time a string is  added
to  the hash table,  so one need not search for the  most  recent
match.

Main Dictionary - Layered Binary Search Tree

     This  approach combines the speed of a hash table  with  the
low  memory requirement of a binary search tree.   As before  you
need  an  array  of  structures,  one  for  each  string  in  the
dictionary.   In  addition  you will need a  variable  number  of
structures  which point to the same strings,  but are located  in
lower layers.   The worst case is also the same as the number  of
strings  in the dictionary,  for a total of twice the RAM  needed
for a simple binary search tree.
     The structures used here are given by:

typedef struct search {
  struct search *child1;  /* less than */
  struct search *child2;  /* greater than */
  struct search *next;    /* start of next tree */
  unsigned char *text;    /* string pointer */
  unsigned int sum;       /* sum of all children */
  unsigned char len;      /* number of common chars */
  unsigned char test;     /* first uncommon char */
 } NODE;

The 'len' parameter is constant over a layer.   The 'test'  entry
is redundant,  where p->test = p->text[p->len],  but is faster to
access  and is free (since structures always take an even  number
of bytes).
     Given a pointer to the start of the tree,  one would compare
the first byte against 'test' and perform the usual binary search
via 'child1' and 'child2'.  If a match is found, 'next' points to
the start of another binary search tree,  but not necessarily for
the second byte.   One would first have to check all the bytes in
p->text[1]  through  p->text[p->len - 1] (where p points  to  the
first entry in the next layer).   If they all match, one can then
search  for  a  matching 'test' using the binary  tree  for  this
layer, etc.
     The  advantage is again that you need only search  for  each
byte once.   Also,  when you find a match of a given length,  the
number  of matching entries is given either by 'sum' (if you  are
between layers), 'next->sum' (if it exists), or is 1.
     The trick is to copy the parent structure (at least, it uses
the  same 'text' pointer) whenever you start an new  layer,  then
add the new string as a child structure of the copy.   Similarly,
whenever  you remove a string from the dictionary,  you  have  to
search the next layer to find the duplicate,  replace the  parent
with an structure from the next layer,  and replace the duplicate
with  a  copy of the new parent (unless there are no more entries
on that layer).  It should be remembered that the duplicate to be
removed might also have a duplicate in the next layer.

Tree Balancing

     Consider the two binary search trees organised as follows:

                   A                   C
                    \                 /
                     \               /
                      C             A
                     /               \
                    B                 B

where A < B < C by value.  It should be noted that any additional
children of A B or C would remain in place if one were to convert
from one to the other.  This transformation is called a rotation.
     Starting  with A using the left tree,  suppose we wanted  to
add a new node D > C.   Starting at A we see that we need to move
to right.  However, before doing so we check to see if the number
of children to the right (child2->sum) is greater than the number
of  children to the left (child1->sum).   If so,  we perform  the
rotation.   Since we are now at C instead of A, we need to repeat
the comparison.  Also, before moving down we should increment the
'sum' entry at C.
     One  can  avoid the need for a parent pointer by  using  the
approach:

HASH *p,**from;

  from = &start;
  p = *from;
  while(p) {
    ...
    if(byte < p->test) from = &(p->child1);
    else if(byte > p->test) from = &(p->child2);
    else from = &(p->next);
    p = *from;
   }

Changing '*from' will change the appropriate pointer,  no  matter
where it came from.


Fine Tuning

     The following table shows the results for various methods of
choosing  which  matches to use.   The first number is  the  time
required  to perform the compression (accurate to 2 seconds)  and
the second is the size of the file.   The 'ZIP' entry is used for
comparison (times are not available).


       | DEMONSTR.DOC | ELFBACK.PRG | WORDLIST.TXT |
-------+--------------+-------------+--------------+
   ZIP |       25134  |      32417  |      496876  |
 Smart |  18   22284  |  22  32567  | 418  503524  |
  Best | 102   22029  |  64  31997  |1670  453142  |
 Best1 |  76   21746  |  54  32451  |1654  446201  |
 Best2 |  70   21960  |  50  32372  |1454  446607  |
-------+--------------+-------------+--------------+
    8K |  20   22444  |  22  32405  | 424  496712  |
   384 |  60   21979  |  40  32417  |1190  419201  |
 8K384 |  60   22133  |  40  32288  |1164  421197  |
-------+--------------+-------------+--------------+

     The 'Smart' method is essentially the same as that developed
in the previous report.   It looks for the longest combination of
two strings.   To decide between a string from the FIFO buffer or
the main dictionary,  each match is ranked by the weight for that
offset times the total number of entries in the main  dictionary,
or the sum of matches in the main dictionary times the sum of all
the  weights  for  the  FIFO  buffer.    To  decide  between  two
combinations of strings which have the same combined  length,  it
looks at the rank times the length of the first match.   This  is
the fastest method which is still competitive with ZIP.
     The 'Best' method looks at all possible ways to compress the
next 65 bytes until a unique first step is determined.   Analysis
by  the  Pure  Profiler showed that most of  time  is  now  spent
computing the number of bits needed to code strings,  rather than
searching for them.
     'Best1' shows a variation of the 'Best' algorithm which only
codes a single byte using arithmetic if there is no other way  to
get to the next byte.   'Best2' also checks if the number of bits
used to get to the end of the longest combination found so far is
less  than the number of bits needed to get to the current  byte,
in  which case it doesn't bother to test if any strings  starting
from  the current byte will help.   While these  variations  only
achieve marginal improvements in speed, there is very little loss
of  compression,  and sometimes they even out-perform the  'Best'
algorithm.
     The  best  thing about all these methods is  that  they  are
totally  compatible  with  the current  versions  of  ELFARC  and
ELFBACK.   However,  if  we relax  this  requirement,  additional
savings are possible.
     '8K'  shows  the  'Smart' algorithm results  when  the  main
dictionary  is  reduced  from 16K to 8K  entries  (640K  to  320K
bytes).  Note that this method beats ZIP on all three files.
     '384' is a variation of 'Best2' which uses 384 codes instead
of 320.   Specifically,  these consist of the 256 basic codes, 64
length codes for the FIFO buffer and 64 length codes for the main
dictionary.   This  was  intended to reduce the number  of  steps
needed to code a string (or compute the number of bits needed  to
code  a string).   Whether it benefits of hurts  the  compression
depends  on whether the distribution of lengths are  similar  for
the  two dictionaries.  '8K384' uses both an 8K  main  dictionary
and the 384 codes.   Interestingly,  using 384 codes had  benefit
for the 'Smart' algorithm whatsoever.
     I also discovered that a very minor improvement in speed  is
possible  by sorting the codes in the arithmetic  compression  so
that the most common codes are close together.

Conclusion

     At  this  point  the difference  in  compression  efficiency
between  Smart  and  Best approaches is  minor  compared  to  the
difference in speed.   Since the '8K' method satisfies the design
criteria,  it will be used for the next versions of both  ELFBACK
and ELFARC.